class Solution {
public:
    vector<unordered_set<char> > edges;
    Solution():edges(26){}
    unordered_map<char,int> indeg;
    bool compare(string s1,string s2){
        for(char& e : s1){
            if(!indeg.count(e)){
                indeg[e] = 0;
            }
        }
        for(char& e : s2){
            if(!indeg.count(e)){
                indeg[e] = 0;
            }
        }
        int i = 0;
        for(i = 0;i < s1.size() && i < s2.size();i++){
            if(s1[i] != s2[i]){
                if(!edges[s1[i] - 'a'].count(s2[i])){
                    edges[s1[i] - 'a'].insert(s2[i]);
                    indeg[s2[i]]++;
                }
                return true;
            }
        }
        if(i < s1.size()) return false;
        return true;
    }
    string alienOrder(vector<string>& words) {
         string ret;
        if(words.size() == 0 ) return ret;
        for(int i = 1;i < words.size();i++){
            bool sb = compare(words[i-1],words[i]);
            if(sb == false) return ret;
        }
        if(indeg.size() == 0) return words[0];
        queue<char> qe;
        for(const pair<char,int>& kv : indeg){
            if(kv.second == 0){
                qe.push(kv.first);
            }
        }
        while(!qe.empty()){
            char x = qe.front();
            qe.pop();
            ret += x;
            for(const char& y : edges[x-'a']){
                indeg[y]--;
                if(indeg[y] == 0){
                    qe.push(y);
                }
            }
        }
        if(ret.size() < indeg.size()) return "";
        return ret;
    }
};

